home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / aijournl / 1986_11 / proced.nov < prev   
Text File  |  1986-09-25  |  5KB  |  166 lines
  1.  
  2.                 Procedural Programming vs. PROLOG
  3.                           by Marc Kenig
  4.                 November 1986 AI EXPERT magazine
  5.  
  6.  
  7.                             Listing 1 
  8.  
  9. PROLOG and Lisp programs. The PROLOG version involves a 'generate 
  10. and test' strategy to find the greatest roman numeral value
  11. 'Z' less than 'X'.It can be extended to larger values by 
  12. simply adding more 'roman' facts. To extend the Lisp version, 
  13. however, both functions must be extended. 
  14.  
  15.  
  16. Lisp       Prolog
  17. (ROMAN
  18.  (LAMBDA (X)     roman(50,"L").
  19.    (SELECTQ X     roman(40,"XL").
  20.      (50 '(L))  (40 '(X L))     roman(10,"X").
  21.      (10 '(X))  (9  '(I X)))       fact database     roman(9,"IX").
  22.      (5  '(V))  (4  '(I V)))     roman(5,"V").
  23.      (1  '(I))  (0  '())     roman(4,"IV").
  24.      (ROMRUL X))     roman(1,"I").
  25. ))     roman(0," ").)
  26.  
  27. (ROMRUL
  28.  (LAMBDA (X)      romrul(X,Y) :-
  29.     (COND ((LESSP 40 X)     X roman Y
  30.     (APPEND (ROMAN 40) (ROMAN (MINUS X 40))))      romrul(X,Y) :-
  31.   ((LESSP 10 X) rules     roman(Z,X1),     --GENERATE
  32.     (APPEND (ROMAN 10) (ROMAN (MINUS X 10))))     Z<X,      --TEST
  33.   ((LESSP 5 X)     Y1 is X mod Z,
  34.     (APPEND (ROMAN 5)  (ROMAN (MINUS X 5))))     romrul(Y1,Z1),
  35.    ((LESSP 1 X)      append(X1,Z1,Y).
  36.     (APPEND (ROMAN 1)  (ROMAN (MINUS X 1))))
  37.     )
  38. ))
  39.  
  40.  
  41. (ROMAN 49)   roman(49,X)
  42.                X = ["XLIX"] ;
  43. (X L I X)
  44.  
  45. Note:   Running/querying each program. The clever though 
  46. unpredictable PROLOG output is due to unchecked backtracking.
  47.  
  48.  
  49.  
  50.                             Listing 2 
  51.  
  52. Corrected version of PROLOG program with cut added as a subgoal 
  53. to curtail unwanted backtracking.
  54.  
  55.  
  56. roman(50,"L").
  57. roman(40,"XL").
  58. roman(10,"X").
  59. roman(9,"IX").
  60. roman(5,"V").
  61. roman(4,"IV").
  62. roman(1,"I").
  63. roman(0," ").
  64.  
  65. romrul(X,Y) :- roman(X,Y) , !
  66.  
  67. romrul(X,Y) :- roman(Z,Y),
  68.        Z<X,
  69.        Y1 is X mod Z,
  70.        romrul(Y1,Z1),
  71.                !,
  72.        append(X1,Z1,Y).
  73.  
  74.  
  75.  
  76.                             Listing 3 
  77.  
  78. The "for" and infinite loops both rely on backtracking and 
  79. recursion to to implement a loop in PROLOG. The sub-goal inf 
  80. causes PROLOG to look in it's rule database and find the 
  81. definition of inf infinitely.
  82.  
  83.  
  84.  
  85.          FOR loop                                      Infinite loop
  86.          --------                                      -------------
  87.  
  88. for(X,[X,Z]) :- X=<Z.                                   
  89. for(X,[Y,Z]) :- W is Z+1,                              inf :- write('hi '),
  90.                 W=<Z,                                         inf.
  91.                 FOR(X,[W,Z]).
  92.  
  93. ?- for(X,[1,10]), write(X), write(' ').                ?- inf.
  94. 1 2 3 4 5 6 7 8 9 10                                   hi hi hi hi hi hi.....
  95. yes.
  96.  
  97.  
  98.  
  99.    Listing 4 - The many ways to query the SAME relation.
  100.  
  101. Definition of relation append:
  102.  
  103.                append([],X,X).
  104.                append([X|Y],Z,[X|X1]) :- append(Y,Z,X1).
  105.  
  106. has four distinct uses based on the arguments supplied.
  107.                                    |
  108. ?- append([a,b], [c,d], X).        |     ?- append([a,b], X, [a,b,c,d]).
  109.                                    |
  110.   X = [a,b,c,d]                    |       X = [c,d]
  111.                                    |
  112.   4a- List concatenation           |    4b - Splitting the list after [a,b]
  113. _______________________________________________________________________________
  114.                                    |
  115. ?- append(X, Y, [a,b,c,d])         |     ?- append([a,b], [c,d], [a,b,c,d]).
  116.    |
  117.   X = []                           | yes
  118.   Y = [a,b,c,d]                    |
  119.   X = [a]                          |     ?- append([a,b], [w,d], [a,b,c,d]).
  120.   Y = [b,c,d]                      |
  121.   X = [a,b]                        |     no
  122.   Y = [c,d]                        |
  123.   X = [a,b,c]                      |
  124.   Y = [d]                          |
  125.   X = [a,b,c,d]                    |
  126.   Y = []                           |
  127.    |     4d - Verifying proper concatenation
  128. 4c - All possible sub-lists pairs  |          of lists
  129.  
  130.  
  131.                             Listing 5 
  132.  
  133. An interactive PROLOG "binary search" guessing game with a sample 
  134. run. The adjust rule exchanges the high and low search limits 
  135. based on the user's input. 
  136.  
  137. game(X)        :- guessing(1,X).
  138. guessing(X,Y)  :- average(X,Y,Z) , talk(Z), ttyget(X1),
  139.                   adjust(X,Y,Z,[X1]).
  140.  
  141. average(X,Y,Z) :- Z1 is X+Y, Z is Z1/2.
  142.  
  143. talk(X)        :- nl, write('Is '), display(X), 
  144.                   write(' G)reater  L)ess than or E)qual to your number? ').
  145.  
  146. adjust(X,Y,Z,"L") :- guessing(Z,Y).
  147. adjust(X,Y,Z,"G") :- guessing(X,Z).
  148. adjust(X,Y,Z,"E") :- !, nl, write('I win!').
  149. adjust(X,X,X,_)   :- !, nl, write('Must be '),display(X).
  150.  
  151. ?- game(50).
  152.  
  153. Is 25 G)reater L)ess than or E)qual to your number?  G
  154.  
  155. Is 13 G)reater L)ess than or E)qual to your number?  L
  156.  
  157. Is 19 G)reater L)ess than or E)qual to your number?  G
  158.  
  159. Is 16 G)reater L)ess than or E)qual to your number?  E
  160.  
  161. I win!
  162.  
  163. ?-
  164. 19 G)reater L)ess than or E)qual to your number?  G
  165.  
  166. Is 16 G)reater L)ess than or E)qual to your